package leetcode.code733.FloodFill;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 不做image[x - 1][y] = newColor; Queue超时
 *
 * @author Max
 * @date 2021年8月18日
 * @description
 */
public class Solution73302 extends FloodFill {

	@Override
	public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
		int oldColor = image[sr][sc];
		if (oldColor == newColor)
			return image;
		int len = image.length;
		int wid = image[0].length;
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { sr, sc });
		image[sr][sc] = newColor;
		do {
			int[] arr = q.poll();
			int x = arr[0];
			int y = arr[1];
			if (y > 0) {
				if (image[x][y - 1] == oldColor) {
					image[x][y - 1] = newColor;
					q.add(new int[] { x, y - 1 });
				}
			}
			if (y < wid - 1) {
				if (image[x][y + 1] == oldColor) {
					image[x][y + 1] = newColor;
					q.add(new int[] { x, y + 1 });
				}
			}

			if (x > 0) {
				if (image[x - 1][y] == oldColor) {
					image[x - 1][y] = newColor;
					q.add(new int[] { x - 1, y });
				}
			}
			if (x < len - 1) {
				if (image[x + 1][y] == oldColor) {
					image[x + 1][y] = newColor;
					q.add(new int[] { x + 1, y });
				}
			}
		} while (!q.isEmpty());
		return image;
	}

	public static void main(String[] args) {
		Solution73302 so = new Solution73302();
		so.debug1();
	}

}
